package Sort;

import java.util.Arrays;

public class MergeSort {

  public static void main(String[] args) {

    int[]num = new int[]{8,4,5,7,1,3,6,2};
    int[]temp = new int[num.length];
    mergeSort(num,0, num.length - 1,temp);

    System.out.println("排序后：" + Arrays.toString(num));
  }

  //分+合方法
  public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if(left < right) {
      int mid = (left + right) / 2; //中间索引
//向左递归进行分解
      mergeSort(arr, left, mid, temp);
//向右递归进行分解
      mergeSort(arr, mid + 1, right, temp);
//到合并
      merge(arr, left, mid, right, temp);
    }
  }


  /*
  arr排序的原始数组
  left左边有序序列的初始索引
  mid中间索引
  right右边索引
  temp中转的数组
   */
  public static void merge(int[]arr,int left,int mid,int right,int[] temp){
    int i = left;//左边有序序列的初始索引
    int j = mid + 1;//右边有序序列的初始索引
    int t = 0;//指向temp数组的当前索引

    //（一）
    //先把左右两边(有序)的数据按照规则填充到temp数组
    //直到左右两边的有序序列，有一边处理完毕为止
    while (i <= mid && j <= right){
    //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
    //将左边的当前元素，填充到temp数组
    //然后t++, 1++
      if (arr[i] < arr[j]){
        temp[t] = arr[i];
        t++;
        i++;
      }
      if (arr[i] > arr[j]){
        temp[t] = arr[j];
        t++;
        j++;
      }
    }

    //(二)
    //把有剩余数据的一边的数据依次全部填充到temp
    while( i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp
      temp[t] = arr[i];
      t++;
      i++;
    }
    while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
      temp[t] = arr[j];
      t++;
      j++;
    }

    //(三)
    //将temp数组的元素拷贝到arr
    //注意，并不是每次都拷贝所有
    t=0;
    int tempLeft = left;
    System.out.println("tempLeft：" + tempLeft + " " + "right:" + right);
    while(tempLeft <= right) {
      arr[tempLeft] = temp[t];
      t++;
      tempLeft++;
    }


  }
}
